package airthmetic.exercise.recursion;

import java.util.ArrayList;
import java.util.List;

public class _22_括号生成 {

    // 递推公式xxx,其中 退出递归的终止条件是，字符串内的左右括号达到给定数量
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        recur(0,0,n,"", res);
        return res;
    }

    public static void recur(int left, int right, int n, String s, List<String> res){
        if(left == n && right == n){
            res.add(s);
            return;
        }
        if(left < n){
            String s1 = s + "(";
            recur(left+1,right,n,s1,res);
        }

        if(right < left){
            String s2 = s + ")";
            recur(left,right+1,n,s2,res);
        }
    }



    // 拆分为左括号和右括号+剪枝
    public static void main(String[] args) {
        generateParenthesis(3);

    }


}
